\section{Upper-bound on the WCRT for a self-suspending task with multiple self-suspending regions}
\label{sec:MILP}

The exact test proposed in the previous section, although restricted to one suspension region, rapidly becomes intractable. In this section, we therefore propose an MILP formulation for computing an upper-bound on the WCRT of a self-suspending task with \emph{multiple} suspension regions when all the interfering tasks are non-self-suspending. This formulation will be extended in the next section to consider the case where multiple self-suspending tasks interfere with each other.

The optimization problem, defined by Expressions~\eqref{opt:objective} to~\eqref{opt:busyperiod} (explained below), has the objective to maximize the sum of the response times of every execution region of $\sstask$. Its constraints~\eqref{opt:ub}--\eqref{opt:busyperiod} can all be easily linearized (see \cite{Kim:RTSS13} for instance). In the proposed problem formulation, the number of jobs $\NI{k,j}$ of each task $\tau_k \in \hp{ss}$ interfering with each execution region of $\sstask$ are integer variables, while the response time $R_{ss,j}$ of each execution region $\ssregion{j}$ of $\sstask$ and the offsets $O_{k,j}$ of each task $\tau_k$ with each execution region $\ssregion{j}$ are real variables. This MILP formulation is quite simple in comparison to the exact test described in Algorithm~\ref{algo:rt1}. As demonstrated in Section~\ref{sec:experiments}, this permits a state-of-the-art MILP solver to output results in an acceptable amount of time for reasonable system sizes.
{\small
\begin{align}
&\textbf{Maximize:}  \quad \sum_{j=1}^{m_{ss}} R_{ss,j} \label{opt:objective} \\
&\textbf{Subject to:}  \nonumber\\ 
& \sum_{j=1}^{m_{ss}} R_{ss,j} + \sum_{j=1}^{m_{ss}-1} S_{ss,j} \leq \UB{} \label{opt:ub}\\
& \forall \ssregion{j} \in \sstask~~:~ R_{ss,j} = C_{ss,j} + \sum\limits_{\tau_p \in \hp{ss}} \NI{p,j} \times C_p 
\label{opt:Rssj} \\
& \qquad\qquad\qquad\quad R_{ss,j} \leq \UB{j} \label{opt:ub_j}\\
%& \forall \tau_k \in \hp{ss}:~ O_{k,1} \geq 0 \label{opt:Ok1} \\
&\forall \tau_k \in \hp{ss}, \forall \ssregion{j} \in \sstask: \nonumber\\ 
& \qquad O_{k,j} \geq 0 \label{opt:Ok1} \\
& \qquad O_{k,j+1} \geq O_{k,j} + \NI{k,j} \times T_k - ( R_{ss,j} + S_{ss,j} ) \label{opt:offset}\\
& \qquad \NI{k,j} \geq 0  \label{opt:NI>0}\\
& \qquad \NI{k,j} \leq \left\lceil \frac{R_{ss,j} - O_{k,j}}{T_k} \right\rceil  \label{opt:ceil}
\end{align}
}
\normalsize

The constraints~\eqref{opt:ub}--\eqref{opt:ceil} of the optimization problem are a direct translation of the constraints already discussed in Section~\ref{sec:oneself}. That is, Constraint~\eqref{opt:Rssj} is equivalent to Eq.~\eqref{eq:resp_ss1}; Constraints~\eqref{opt:Ok1} and \eqref{opt:offset} are a generalization of Eq.~\eqref{eq:offset_ss2} computing the offsets of the higher priority tasks with each execution region; and Constraints~\eqref{opt:NI>0} and \eqref{opt:ceil} impose the traditional lower- and upper-bound on the number of interfering jobs of each task $\tau_k$ with each execution region $\ssregion{j}$ as already discussed for Eq.~\eqref{eq:resp_ss2}. Constraints~\eqref{opt:ub} and~\eqref{opt:ub_j} reduce the research space of the problem by stating that the overall response time of $\sstask$ and the response time of each of its execution region, respectively, cannot be larger than known upper-bounds computed with simple methods such as the joint and split methods presented in \cite{btesas:thesis2007}. 

The solution of the optimization problem can still be improved by adding the following constraint:
\small
\begin{align}
&\forall \tau_k \in \hp{ss}, \forall \ssregion{j} \in \sstask: \nonumber\\
& \quad R_{ss,j} > \release{k}{j} + \sum\limits_{\tau_p \in \hp{ss}} \max\{ 0, ~\left\lfloor \frac{\deadline{p}{j} - \release{k}{j}}{T_p} \right\rfloor  C_p \}\label{opt:busyperiod}
\end{align}
\normalsize
where $\release{k}{j} \equals O_{k,j} + (\NI{k,j}-1)\times T_k$ and $\deadline{p}{j} \equals O_{p,j} + \NI{p,j} \times T_p$.

The value of $\release{k}{j}$ gives the release instant of the last job of $\tau_k$ released in the execution region $\ssregion{j}$, while $\deadline{p}{j}$ gives the deadline of the last job of $\tau_p$ released in $\ssregion{j}$. Therefore, the term $\left\lfloor \frac{\deadline{p}{j} - \release{k}{j}}{T_p} \right\rfloor$ provides the number of jobs released by $\tau_p$ after $\release{k}{j}$ and the sum thus gives the total workload released by higher priority tasks after $\release{k}{j}$. Since $\sstask$ cannot execute when higher priority workload is available and because $\release{k}{j}$ is an instant in the response time of the execution region, the response time of $\ssregion{j}$ cannot be smaller or equal than $\release{k}{j}$ plus the higher priority workload remaining to execute after $\release{k}{j}$. This is what Constraint~\eqref{opt:busyperiod} enforces.

Note that because the optimization problem tests all the possible values for the offsets $O_{k,j}$ of each task $\tau_k$ with every execution region of $\sstask$, it also tests all the possible synchronous release combinations. Therefore, there is no need to impose any constraint on the synchronous release patterns, as it was the case in Algorithm~\ref{algo:rt1}.